package aStar;

import app.env.Data;
import app.env.Position;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
/**
 * @Name: AStarAlgorithm
 * @Description:
 * 把起始格添加到 "开启列表"
 * do
 * {
 *        寻找开启列表中F值最低的格子, 我们称它为当前格.
 *        把它切换到关闭列表.
 *        对当前格相邻的8格中的每一个
 *           if (它不可通过 || 已经在 "关闭列表" 中)
 *           {
 *                 什么也不做.
 *           }
 *           if (它不在开启列表中)
 *           {
 *                 把它添加进 "开启列表", 把当前格作为这一格的父节点, 计算这一格的 FGH
 *           }
 *           if (它已经在开启列表中)
 *           {
 *                 if (用G值为参考检查新的路径是否更好, 更低的G值意味着更好的路径)
 *                     {
 *                             把这一格的父节点改成当前格, 并且重新计算这一格的 GF 值.
 *                     }
 *           }
 *           目标格已经在 "开启列表", 这时候路径被找到跳出循环；
 * } while(开启列表不为空)
 * 如果开启列表已经空了,目标格没找到 说明路径不存在.
 * 最后从目标格开始, 沿着每一格的父节点移动直到回到起始格, 这就是路径.
 * @Author: yfish
 * @Date: 2021/4/25
 */

public class AStarAlgorithm1 {

    private static final int[][] DIREC = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
            {1, 0}, {1, -1}, {0, -1}, {-1, -1}};

    // 10 10 0 0 9 9
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("please enter (xs ys x1 y1 x2 y2): ");
        final int xs = scanner.nextInt();
        final int ys = scanner.nextInt();
        int x1 = scanner.nextInt();
        int y1 = scanner.nextInt();
        int x2 = scanner.nextInt();
        int y2 = scanner.nextInt();
        scanner.close();

        // generate a two-dimension array filled with 0
        int map[][] = new int[xs][ys];
        for (int i = 0; i < xs; i++) {
            int tmp[] = new int[ys];
            Arrays.fill(tmp, 0);
            map[i] = tmp;
        }
        int midr = xs / 2;
        int midc = ys / 2;
        /*map[midr - 1][midc] = 1;
        map[midr][midc] = 1;
        map[midr + 1][midc] = 1;*/

        for (int i = 1; i < xs - 1; i++) {
            map[i][midc] = 1;
        }
        map[0][6] = Data.TARGET_SIGNAL;
        map[2][6] = Data.TARGET_SIGNAL;
        map[3][6] = Data.TARGET_SIGNAL;
        map[4][6] = Data.TARGET_SIGNAL;
        map[5][6] = Data.TARGET_SIGNAL;
        map[6][6] = Data.OBSTACLE_SIGNAL;


        Stack<Position> pos =  findPath(map, x1, y1, x2, y2);
        System.out.println(pos.pop());
        System.out.println("hello");
    }

    public static Stack<Position> findPath(int[][] board, int x1, int y1, int x2, int y2) {



        int[][] DIREC =  {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
                {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
        List<Position> openList = new ArrayList<>();
        List<Position> closeList = new ArrayList<>();
        boolean findFlag = false;
        Position termPos = null;
        // 起始点
        Position startPos = new Position(x1, y1, calcH(x1, y1, x2, y2));
        openList.add(startPos);
        do {
            // 通过在开启列表中找到F值最小的点作为当前点
            Position currentPos = openList.get(0);

            for (Position position : openList) {
                if (currentPos.F > position.F) {
                    currentPos = position;
                }
            }
            // 将找到的当前点放到关闭列表中，并从开启列表中删除
            closeList.add(currentPos);
            openList.remove(currentPos);

            //遍历当前点对应的4个相邻点
            for (int[] direc : DIREC) {
                int tmpX = currentPos.x + direc[0];
                int tmpY = currentPos.y + direc[1];
                if (tmpX < 0 || tmpX >= board.length || tmpY < 0 || tmpY >= board[0].length) {
                    continue;
                }
                //创建对应的点
                Position tmpPos = new Position(tmpX, tmpY, calcH(tmpX, tmpY, x2, y2), currentPos);
                //board中对应的值时障碍物或目标， 或对应的点已经在关闭列表中
                if (board[tmpX][tmpY] == Data.OBSTACLE_SIGNAL ||
                        board[tmpX][tmpY] == Data.TARGET_SIGNAL ||
                        closeList.contains(tmpPos)) {
                    continue;
                }
                //如果不在开启列表中，则加入到开启列表
                if (!openList.contains(tmpPos)) {
                    openList.add(tmpPos);
                } else {
                    // 如果已经存在开启列表中，则用G值考察新的路径是否更好，如果该路径更好，则把父节点改成当前格并从新计算FGH
                    Position prePos = null;
                    for (Position pos : openList) {
                        if (pos.x == tmpX && pos.y == tmpY) {
                            prePos = pos;
                            break;
                        }
                    }
                    if (tmpPos.G < prePos.G) {
                        prePos.setFatherPos(currentPos);
                    }
                }
            }
            // 判断终点是否在开启列表中
            for (Position tpos : openList) {
                if (tpos.x == x2 && tpos.y == y2) {
                    termPos = tpos;
                    findFlag = true;
                    break;
                }
            }

        } while(openList.size() != 0);

        if(!findFlag) {
            System.out.println("no valid path!");
            return null;
        }

        Stack<Position> resStack = new Stack<Position>();

        if (termPos != null) {
            resStack.push(termPos);
            while(termPos.father != null) {
                termPos = termPos.father;
                resStack.push(termPos);
            }
        }
        return resStack;
    }


    /**
     * 计算某个格子的H值
     * @param x
     * @param y
     * @param tx 终点的x值
     * @param ty 终点的y值
     * @return
     */
    private static int calcH(int x, int y, int tx, int ty) {
        int diff = Math.abs(x - tx) + Math.abs(y - ty);
        return diff * 10;
    }
}

